GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Max-Flow-Min-Cut-Theorem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Max-Flow-Min-Cut-Theorem</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Auf dem Gebiet der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> bezeichnet das Max-Flow-Min-Cut-Theorem einen <a href="Satz_(Mathematik)" title="Satz (Mathematik)">Satz</a>, der eine Aussage über den Zusammenhang von <a href="Fl%C3%BCsse_und_Schnitte_in_Netzwerken" title="Flüsse und Schnitte in Netzwerken">maximalen Flüssen</a> und minimalen <a href="Schnitt_(Graphentheorie)" title="Schnitt (Graphentheorie)">Schnitten</a> eines <a href="Flussnetzwerk" class="mw-redirect" title="Flussnetzwerk">Flussnetzwerkes</a> gibt. Der Satz besagt:

<dl><dd>Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts.</dd></dl>

Der Satz ist eine Verallgemeinerung des <a href="Satz_von_Menger" title="Satz von Menger">Satzes von Menger</a>. Er wurde im Jahr 1956 unabhängig von <a href="Lester_Randolph_Ford_junior" title="Lester Randolph Ford junior">L.R. Ford Jr.</a> und <a href="Delbert_Ray_Fulkerson" title="Delbert Ray Fulkerson">D.R. Fulkerson</a>, sowie von <a href="Peter_Elias" title="Peter Elias">P. Elias</a>, A. Feinstein und <a href="Claude_Elwood_Shannon" class="mw-redirect" title="Claude Elwood Shannon">C.E. Shannon</a> bewiesen.<a href="#cite_note-FF-1">[1]</a><a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7dc43221ee885a10b87c89373b12b8c1110e7ca5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.233ex; height:2.843ex;" alt="{\displaystyle G(V,E)}" loading="lazy"> ein endlicher <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteter Graph</a> mit den <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> und den <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy">. Jede Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (u,v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eadf12294edccd7a29c99cfc1765e4a14bf47e58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.301ex; height:2.843ex;" alt="{\displaystyle (u,v)}" loading="lazy"> vom Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> zum Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> habe eine nichtnegative Kapazität <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(u,v).}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(u,v).}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2ae7839adfdfddc512a66c2225b07d1a9475060a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.954ex; height:2.843ex;" alt="{\displaystyle c(u,v).}" loading="lazy"> Außerdem gibt es einen Quellknoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">, in dem der Netzwerkfluss beginnt, und einen Zielknoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, in dem der Netzwerkfluss endet.

Ein Schnitt ist eine Aufteilung der Knoten in zwei disjunkte Teilmengen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> für die gilt, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\in S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\in S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/acce52dffd84d073a24f4606a175da60148fd0c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.43ex; height:2.176ex;" alt="{\displaystyle s\in S}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4fe93f70df3818ecca67c2ca44f087483951856.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.317ex; height:2.176ex;" alt="{\displaystyle t\in T}" loading="lazy">. Die Kapazität eines Schnittes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (S,T)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (S,T)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/467faf91b93aed51e1dd1c656f1ae71d9c922a38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.979ex; height:2.843ex;" alt="{\displaystyle (S,T)}" loading="lazy"> ist die Summe aller Kantenkapazitäten von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> nach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">, also

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(S,T)=\sum _{u\in S,v\in T|(u,v)\in E}c(u,v)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2e98ea4cf60769997ca9941d548120463f127981.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:29.667ex; height:6.009ex;" alt="{\displaystyle c(S,T)=\sum _{u\in S,v\in T|(u,v)\in E}c(u,v)}" loading="lazy">.</dd></dl>

Die folgenden drei Aussagen sind äquivalent:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> ist der maximale Fluss in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">.</li>

<li>Das <a href="Residualnetzwerk" class="mw-redirect" title="Residualnetzwerk">Residualnetzwerk</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.963ex; height:2.843ex;" alt="{\displaystyle G_{f}}" loading="lazy"> enthält keinen <a href="Augmentierender_Pfad" class="mw-redirect" title="Augmentierender Pfad">augmentierenden Pfad</a>.</li>

<li>Für mindestens einen Schnitt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (S,T)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (S,T)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/467faf91b93aed51e1dd1c656f1ae71d9c922a38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.979ex; height:2.843ex;" alt="{\displaystyle (S,T)}" loading="lazy"> ist der <a href="Fl%C3%BCsse_und_Schnitte_in_Netzwerken#Wert" title="Flüsse und Schnitte in Netzwerken">Wert</a> des Flusses gleich der <a href="Fl%C3%BCsse_und_Schnitte_in_Netzwerken#Schnitt" title="Flüsse und Schnitte in Netzwerken">Kapazität des Schnittes</a>: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f|=c(S,T)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f|=c(S,T)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67ec3a6b92b47b9ca46f0ea5de31810327f9b918.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.656ex; height:2.843ex;" alt="{\displaystyle |f|=c(S,T)}" loading="lazy"></li></ol>

<div class="mw-heading mw-heading3"><h3 id="Beweisskizze">Beweisskizze</h3></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\Rightarrow 2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2a4336b3d8f3141c8e25af1c552c7b67e4b0e120.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.939ex; height:2.176ex;" alt="{\displaystyle 1\Rightarrow 2}" loading="lazy"> Wenn es einen augmentierenden Pfad gäbe, so könnte man den Fluss entlang dessen vergrößern; somit kann der Fluss nicht maximal gewesen sein.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\Rightarrow 3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce983be0cf4efdcf5cbe6f49500f30c0a6530dcf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.939ex; height:2.176ex;" alt="{\displaystyle 2\Rightarrow 3}" loading="lazy"> Wenn es keinen augmentierenden Pfad gibt, dann teile den Graph in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy">, die von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> im Residualnetzwerk erreichbaren Knoten, und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">, den Rest. Dann ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(S,T)-|f|=0}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(S,T)-|f|=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/296083efc07a0b1771aabd9b88ff3abcd5876774.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.659ex; height:2.843ex;" alt="{\displaystyle c(S,T)-|f|=0}" loading="lazy"> (wäre es nicht 0, so wäre <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> doch erreichbar gewesen). Dann ist für diesen Schnitt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f|=c(S,T)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f|=c(S,T)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67ec3a6b92b47b9ca46f0ea5de31810327f9b918.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.656ex; height:2.843ex;" alt="{\displaystyle |f|=c(S,T)}" loading="lazy">.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3\Rightarrow 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ccde545dc1eb9f5b7be7250e2d6feff361562f57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.939ex; height:2.176ex;" alt="{\displaystyle 3\Rightarrow 1}" loading="lazy"> Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> nicht maximal wäre, so könnte man ihn vergrößern. Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> kleiner gleich der Kapazität eines jeden Schnitts ist, kann für mindestens einen Schnitt die Kapazität noch nicht ausgenutzt sein; darüber hinaus gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f|=c(S,T)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f|=c(S,T)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67ec3a6b92b47b9ca46f0ea5de31810327f9b918.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.656ex; height:2.843ex;" alt="{\displaystyle |f|=c(S,T)}" loading="lazy"> für keinen Schnitt, weil sonst kein augmentierender Pfad für die Flussvergrößerung bestünde und der Fluss maximal wäre.</li></ul>

Insbesondere zeigt dies, dass der maximale Fluss gleich dem minimalen Schnitt ist: Wegen 3. hat er die Größe mindestens eines Schnitts, also mindestens des kleinsten, und wegen 2. auch höchstens diesen Wert, weil das Residualnetzwerk bereits keinen augmentierenden Pfad mehr enthalten kann, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |f|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |f|}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/940e58aa437f429f47fd743a819e41fedaa1ff9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.572ex; height:2.843ex;" alt="{\displaystyle |f|}" loading="lazy"> die Größe des kleinsten Schnitts erreicht hat.

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

Sei das Flussnetzwerk mit den Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V=\{s,o,p,q,r,t\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V=\{s,o,p,q,r,t\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/515a4c20c2c5e32e51ba48b209fb43d76078dac0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.726ex; height:2.843ex;" alt="{\displaystyle V=\{s,o,p,q,r,t\}}" loading="lazy"> gegeben, und ein maximaler Fluss von der Quelle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> zur Senke <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> der Größe 5.

Es gibt drei minimale Schnitte in diesem Netzwerk:

<th>Schnitt</th>

<th>Kapazität

</th></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}=\{s,p\},T=\{o,q,r,t\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/09ce72363e2e1301dbc353beed97110120cfe2d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.477ex; height:2.843ex;" alt="{\displaystyle S_{1}=\{s,p\},T=\{o,q,r,t\}}" loading="lazy">

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(s,o)+c(p,r)=3+2=5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e277b8c4dd6da41a42fae4ea0091b1511fd7838d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.501ex; height:2.843ex;" alt="{\displaystyle c(s,o)+c(p,r)=3+2=5}" loading="lazy">

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}=\{s,o,p\},T=\{q,r,t\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e9cd82dcf9b1282fb726e828444ae6af91900715.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.477ex; height:2.843ex;" alt="{\displaystyle S_{2}=\{s,o,p\},T=\{q,r,t\}}" loading="lazy">

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(o,q)+c(p,r)=3+2=5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe526bea89fe0363b4c2ea8727499080630313bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.48ex; height:2.843ex;" alt="{\displaystyle c(o,q)+c(p,r)=3+2=5}" loading="lazy">

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{4}=\{s,o,p,q,r\},T=\{t\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0458a271f0cdee61b2575d81d5a9233277c5eb16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.477ex; height:2.843ex;" alt="{\displaystyle S_{4}=\{s,o,p,q,r\},T=\{t\}}" loading="lazy">

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(q,t)+c(r,t)=2+3=5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca1ae88eb8d422cdc2c79b61aeaee8f190c37c11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.863ex; height:2.843ex;" alt="{\displaystyle c(q,t)+c(r,t)=2+3=5}" loading="lazy">

</td></tr></tbody></table>

Anmerkung: Bei allen anderen Schnitten ist die Summe der Kapazitäten (nicht zu verwechseln mit dem Fluss) der ausgehenden Kanten größer gleich 6. Zum Beispiel ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\{s,o\},T=\{q,p,r,t\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=\{s,o\},T=\{q,p,r,t\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b0c1ed20e96b1c1db7f44e8d3dfcc1431cc9e2d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.497ex; height:2.843ex;" alt="{\displaystyle S=\{s,o\},T=\{q,p,r,t\}}" loading="lazy"> kein minimaler Schnitt, da die Summe der Kapazitäten der ausgehenden Kanten gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(o,q)+c(o,p)+c(s,p)=3+2+3=8}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(o,q)+c(o,p)+c(s,p)=3+2+3=8}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a53bd6787df07b2098278aad9b6df7254198e633.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.513ex; height:2.843ex;" alt="{\displaystyle c(o,q)+c(o,p)+c(s,p)=3+2+3=8}" loading="lazy"> ist. Des Weiteren ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{5}=\{s,o,p,r\},T=\{q,t\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{5}=\{s,o,p,r\},T=\{q,t\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/589ebe76ad7ec0ba69aad4fed50e039bbf091f69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.477ex; height:2.843ex;" alt="{\displaystyle S_{5}=\{s,o,p,r\},T=\{q,t\}}" loading="lazy"> kein minimaler Schnitt, obwohl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (o,q)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (o,q)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83c38a739db412b4a66b78e9f4207a603e7aa0e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.04ex; height:2.843ex;" alt="{\displaystyle (o,q)}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (r,t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (r,t)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0296bfb5016c49095d0dbef2d5dbd3304eae2903.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.732ex; height:2.843ex;" alt="{\displaystyle (r,t)}" loading="lazy"> voll genutzt werden; denn es gibt im Residualnetzwerk <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.963ex; height:2.843ex;" alt="{\displaystyle G_{f}}" loading="lazy"> noch eine Kante (r,q) der Restkapazität <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d33c0387745788a5acf2518e37fda6de360fd304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:41.394ex; height:3.009ex;" alt="{\displaystyle c_{f}(r,q)=c(r,q)-f(r,q)=0-(-1)=1}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Algorithmus_zum_Finden_minimaler_Schnitte">Algorithmus zum Finden minimaler Schnitte</h3></div>

Es gibt verschiedene Algorithmen zum Finden minimaler Schnitte. Der folgende Algorithmus findet die Kanten eines minimalen Schnittes direkt aus dem Residualnetzwerk und macht sich damit die Eigenschaften des Max-Flow-Min-Cut-Theorems zu Nutze. Der Restflussgraph kann zum Beispiel mit Hilfe des <a href="Algorithmus_von_Ford_und_Fulkerson" title="Algorithmus von Ford und Fulkerson">Algorithmus von Ford und Fulkerson</a> erzeugt werden.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> ein endlicher gerichteter Graph mit einer Quelle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">, einer Senke <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> und jede Kante habe eine nichtnegative Kapazität.

findeKantenEinesMinCut(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">)

1 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}\leftarrow }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}\leftarrow }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1ec0ff261cf1ea74fec16cc2ddb17d948c1ad712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.932ex; height:2.843ex;" alt="{\displaystyle G_{f}\leftarrow }" loading="lazy">Residualnetzwerk(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">)

2 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\leftarrow \emptyset }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\leftarrow \emptyset }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1251bc113aa0c904f25a29cfe63f8829948c0176.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.276ex; height:2.509ex;" alt="{\displaystyle S\leftarrow \emptyset }" loading="lazy">

3 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\leftarrow \emptyset }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\leftarrow \emptyset }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53b625313ab123b41c1f44b68a25d9e6ef23ce82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.413ex; height:2.509ex;" alt="{\displaystyle T\leftarrow \emptyset }" loading="lazy">

4 Für jeden Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/99886ebbde63daa0224fb9bf56fa11b3c8a6f4fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.756ex; height:2.176ex;" alt="{\displaystyle v\in V}" loading="lazy">

5 Wenn Pfad(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s,v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s,v}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b7f0fffd3599d91e9e29edf4031ef8fbafc5dff4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.252ex; height:2.009ex;" alt="{\displaystyle s,v}" loading="lazy">) in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{f}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86fb9e8d359d1eacb9be564288c4f2f64ce44ab2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.963ex; height:2.843ex;" alt="{\displaystyle G_{f}}" loading="lazy"> existiert

6 dann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\leftarrow S\cup \{v\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\leftarrow S\cup \{v\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/708410f4547722981f5f75940fea68f323c60209.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.648ex; height:2.843ex;" alt="{\displaystyle S\leftarrow S\cup \{v\}}" loading="lazy">

7 ansonsten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\leftarrow T\cup \{v\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\leftarrow T\cup \{v\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d958b14ac6c2da5c566034760c56f5361fb1fb70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.922ex; height:2.843ex;" alt="{\displaystyle T\leftarrow T\cup \{v\}}" loading="lazy">

8 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\leftarrow \emptyset }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\leftarrow \emptyset }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a65df4200cec9f533ae0d363d828ca1c95e67051.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.543ex; height:2.509ex;" alt="{\displaystyle C\leftarrow \emptyset }" loading="lazy">

9 Für jede Kante <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e\in E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e\in E}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34778736d9c6d607a4da3d25594b38dd3e8c82ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.7ex; height:2.176ex;" alt="{\displaystyle e\in E}" loading="lazy">

10 Wenn startKnoten(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">)<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \in S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \in S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/813129d6e4794d5b9c99a446b2c3683c29a539fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.695ex; height:2.176ex;" alt="{\displaystyle \in S}" loading="lazy"> und endKnoten(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">)<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \in T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \in T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a2415d728a2b1eb93f636a21799f3ba35d8df59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.832ex; height:2.176ex;" alt="{\displaystyle \in T}" loading="lazy"> liegt

11 dann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\leftarrow C\cup \{e\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\leftarrow C\cup \{e\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/523d4e52d42a8f9cdc4b7aacb8cc0ccf23642ecc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.138ex; height:2.843ex;" alt="{\displaystyle C\leftarrow C\cup \{e\}}" loading="lazy">

12 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> ist jetzt die Menge der Kanten für einen minimalen Schnitt

</pre>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> würde im oberen Beispiel die Schnittkanten von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy"> enthalten.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Thomas H. Cormen, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" title="Ronald L. Rivest">Ronald L. Rivest</a>, Clifford Stein: Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7. Chapter 26: Maximum Flow, S. 643–700.</li>

<li>Santanu Saha Ray: <cite style="font-style:italic">Graph Theory with Algorithms and its Applications</cite>. Springer India, New Delhi u. a. 2013, ISBN 978-81-322-0749-8, S. 162–165.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Max-Flow-Min-Cut-Theorem&rft.au=Santanu+Saha+Ray&rft.btitle=Graph+Theory+with+Algorithms+and+its+Applications&rft.date=2013&rft.genre=book&rft.isbn=9788132207498&rft.pages=162-165&rft.place=New+Delhi+u.+a.&rft.pub=Springer+India" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-FF-1"><a href="#cite_ref-FF_1-0">↑</a> L.R. Ford Jr., D.R Fulkerson: <cite style="font-style:italic">Maximal flow through a network</cite>. In: <cite style="font-style:italic">Canad. J. Math.</cite> 8. Jahrgang, 1956, S. 399–404, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4153/CJM-1956-045-5">10.4153/CJM-1956-045-5</a> (<a rel="nofollow" class="external text" href="http://cms.math.ca/cjm/v8/cjm1956v08.0399-0404.pdf">math.ca</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Max-Flow-Min-Cut-Theorem&rft.atitle=Maximal+flow+through+a+network&rft.au=L.R.+Ford+Jr.%2C+D.R+Fulkerson&rft.btitle=Canad.+J.+Math.&rft.date=1956&rft.doi=10.4153%2FCJM-1956-045-5&rft.genre=book&rft.pages=399-404&rft.volume=8.+Jahrgang" style="display:none">

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> P. Elias, A. Feinstein, C.E. Shannon: <cite style="font-style:italic">Note on Maximum Flow Through a Network</cite>. In: <cite style="font-style:italic">IRE Trans. on Information Theory, IT</cite>. 2. Jahrgang, Nr. 4, 1956, S. 117–119, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109/TIT.1956.1056816">10.1109/TIT.1956.1056816</a> (<a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304234456/http://www.ece.rice.edu/~camp/MAC/shannon.pdf">ece.rice.edu</a> (<a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a> des <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><a class="external text" href="https://redirecter.toolforge.org/?url=http%3A%2F%2Fwww.ece.rice.edu%2F%7Ecamp%2FMAC%2Fshannon.pdf">Originals</a> vom 4. März 2016 im <a href="Internet_Archive" title="Internet Archive">Internet Archive</a>) [abgerufen am 3. September 2013]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Max-Flow-Min-Cut-Theorem&rft.atitle=Note+on+Maximum+Flow+Through+a+Network&rft.au=P.%26%2332%3BElias%2C%26%2332%3BA.%26%2332%3BFeinstein%2C%26%2332%3BC.E.%26%2332%3BShannon&rft.date=1956&rft.doi=10.1109%2FTIT.1956.1056816&rft.genre=journal&rft.issue=4&rft.jtitle=IRE+Trans.+on+Information+Theory%2C+IT&rft.pages=117-119&rft.volume=2.+Jahrgang" style="display:none">

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-12-14" href="https://de.wikipedia.org/wiki/?title=Max-Flow-Min-Cut-Theorem&oldid=251245396">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>